import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * Klasa uzywana jest do wywolania Klasycznego Algorytmu Genetycznego na
 * instancji problemu podzialu zbioru.
 * 
 * @author Ewa Byra (nr indeksu s6405)
 */
public class GeneticAlgorithm {
	private List<Integer> data;
	private List<Chromosome> population;
	private Random generator = new Random();

	public static final int ROULETTE_WHEEL_SELECTION = 0;
	public static final int TOURNAMET_SELECTION = 1;

	/**
	 * Konstruktor klasy. Przypisuje wartosci z parametrow do zmiennych
	 * klasowych, a nastepnie wywoluje metode getPopulation() losujaca
	 * poczatkowa populacje.
	 * 
	 * @param data
	 *            Lista instancji problemu podzialu zbioru.
	 * @param populationSize
	 *            Wielkosc populacji.
	 */
	public GeneticAlgorithm(List<Integer> data, int populationSize) {
		this.data = data;
		this.population = Population.getPopulation(data, populationSize);
	}

	/**
	 * Glowna metoda sluzaca do wytypowania najlepiej przystosowanego
	 * chromosomu. Opiera sie na klasycznym algorytmie genetycznym. Liczba
	 * generacji jest ograniczona przez parametr. Glowna petla algorytmu ma
	 * nastepujacy przebieg:<br>
	 * 1. Selekcja chromosomow. Wytypowane zostaja osobniki sluzace do
	 * utworzenia puli rodzicielskiej.<br>
	 * 2. Zastosowanie operatorow genetycznych (operator krzyzowania i mutacji).<br>
	 * 
	 * @param generationCount
	 *            Liczba generacji.
	 * @param crossoverParam
	 *            Operator krzyzowania.
	 * @param mutationParam
	 *            Operator mutacji.
	 * 
	 * @return Zwracany jest najepiej przystosowany osobnik ostatniej generacji.
	 */
	public Partition runAlgorithm(int generationCount, double crossoverParam,
			double mutationParam, int selectionMethod) {
		List<Chromosome> selectedChromosomes;
		List<Chromosome> newGeneration;
		double crossover, mutation;

		for (int i = 0; i < generationCount; i++) {
			selectedChromosomes = new ArrayList<>();
			newGeneration = new ArrayList<>();

			/* Selekcja chromosomow */
			if (selectionMethod == ROULETTE_WHEEL_SELECTION)
				selectedChromosomes = rouletteWheelSelection();
			else
				selectedChromosomes = tournamentSelection();

			/* Zastosowanie operatorow genetycznych: */
			/* - Krzyzowania */
			for (int j = 0; j < selectedChromosomes.size() - 1; j += 2) {
				crossover = this.generator.nextDouble();
				if (crossover < crossoverParam)
					newGeneration.addAll(crossover(selectedChromosomes.get(j),
							selectedChromosomes.get(j + 1)));
				else {
					newGeneration.add(selectedChromosomes.get(j));
					newGeneration.add(selectedChromosomes.get(j + 1));
				}
			}
			/*
			 * jezeli ilosc chromosomow w populacji jest nieparzysta, ostatni
			 * zostaje bez pary
			 */
			if (selectedChromosomes.size() % 2 != 0) {
				newGeneration.add(selectedChromosomes.get(selectedChromosomes
						.size() - 1));
			}
			/* - Mutacji */
			this.population = new ArrayList<>();
			for (int j = 0; j < newGeneration.size(); j++) {
				mutation = this.generator.nextDouble();
				if (mutation < mutationParam)
					this.population.add(mutation(newGeneration.get(j)));
				else
					this.population.add(newGeneration.get(j));
			}
		}

		/* Wyznaczanie najlepszego chromosomu */
		Chromosome ch = getTheBestChromosome();
		String code = ch.getBinaryCode();
		List<Integer> firstSet = new ArrayList<>();
		List<Integer> secondSet = new ArrayList<>();

		for (int i = 0; i < this.data.size(); i++) {
			if (code.charAt(i) == '0')
				firstSet.add(this.data.get(i));
			else
				secondSet.add(this.data.get(i));
		}

		return new Partition(firstSet, secondSet);
	}

	/**
	 * Metoda sluzy do wytypowania najlepiej przystosowanych chromosomow, ktore
	 * dadza poczatek nowej generacji. Przy selekcji zastosowano algorytm kola
	 * ruletki (ang. Roulette wheel selection (SCX)). Przebieg algorytmu jest
	 * nastepujacy:<br>
	 * 1. Obliczany jest rozklad prawdopodobienstwa dla kazego z chromosomow na
	 * podstawie jego wartosci przystosowania.<br>
	 * 2. Losowana jest liczba z przedzialu [0, 1], ktora stanowi prog przejscia
	 * chromosomu do nowej generacji.<br>
	 * 3. Dopuki rozmiar listy wytypowanych chromosomow nie bedzie rowny
	 * rozmiarowi populacji:<br>
	 * 3.1. Losowany jest indeks chromosomu w liscie (co ma imitowac krecenie
	 * kolem ruletki)<br>
	 * 3.2. Sprawdzane jest czy chromosom ma wartosc przystosowania ponizej
	 * progu (funkcja przystosowania jest malejaca)<br>
	 * 
	 * @return Lista wytypowanych chromosomow.
	 */
	private List<Chromosome> rouletteWheelSelection() {
		List<Chromosome> selectedChromosomes = new ArrayList<>();
		List<Double> probabilities = new ArrayList<>();
		double fitnessSum = 0;
		double randomDouble;
		double fitnessTMP;
		int index;

		/* Suma wartosci funkcji celu */
		for (int i = 0; i < population.size(); i++) {
			fitnessSum += population.get(i).getFitness();
		}

		/* Rozklad prawdopodobienstwa */
		for (int i = 0; i < population.size(); i++) {
			fitnessTMP = population.get(i).getFitness();
			probabilities.add(fitnessTMP / fitnessSum);
		}

		while (selectedChromosomes.size() < population.size()) {

			/* Losujemy liczbe */
			randomDouble = generator.nextDouble();

			/*
			 * Losujemy index
			 */
			index = generator.nextInt(population.size() - 1);

			/*
			 * Jezeli prawdopodobenstwo chromosomu jest mniejsze od wylosowanej
			 * liczby to chromosom zostaje wybrany
			 */
			if (probabilities.get(index) < randomDouble) {
				selectedChromosomes.add(population.get(index));
				if (selectedChromosomes.size() == population.size())
					break;
			}

		}

		return selectedChromosomes;
	}

	/**
	 * Metoda sluzy do wytypowania najlepiej przystosowanych chromosomow, ktore
	 * dadza poczatek nowej generacji. Przy selekcji zastosowano algorytm
	 * selekcji turniejowej (ang. Tournament selection). Przebieg algorytmu jest
	 * nastepujacy:<br>
	 * Dopuki rozmiar listy wytypowanych chromosomow nie bedzie rowny rozmiarowi
	 * populacji:<br>
	 * 1. Mieszamy liste<br>
	 * 2. Dobieramy osobniki w pary<br>
	 * 3. Z kazdej pary wybieramy osobnika z mniejszya wartoscia przystosowania<br>
	 * 
	 * @return Lista wytypowanych chromosomow.
	 */
	private List<Chromosome> tournamentSelection() {
		List<Chromosome> selectedChromosomes = new ArrayList<>();
		List<Chromosome> temporaryChromosomesList = new ArrayList<>();
		temporaryChromosomesList.addAll(population);
		int fitness1, fitness2;

		while (selectedChromosomes.size() < population.size()) {

			Collections.shuffle(temporaryChromosomesList); /* Mieszanie listy */

			for (int i = 0; i < temporaryChromosomesList.size() - 1; i += 2) {

				fitness1 = temporaryChromosomesList.get(i).getFitness();
				fitness2 = temporaryChromosomesList.get(i + 1).getFitness();

				if (fitness1 < fitness2) {
					selectedChromosomes.add(temporaryChromosomesList.get(i));
				} else
					selectedChromosomes
							.add(temporaryChromosomesList.get(i + 1));

				if (selectedChromosomes.size() == population.size())
					break;
			}

			/*
			 * jezeli ilosc chromosomow w populacji jest nieparzysta, ostatni
			 * zostaje dodany do listy automatycznie
			 */
			if (temporaryChromosomesList.size() % 2 != 0
					&& selectedChromosomes.size() != population.size()) {
				selectedChromosomes.add(temporaryChromosomesList
						.get(temporaryChromosomesList.size() - 1));
			}
		}

		return selectedChromosomes;
	}

	/**
	 * Metoda krzyzowania chromosomow. Losowany jest indeks, ktory bedzie
	 * stanowic punkt przeciecia. Zwraca liste z dwoma osobnikami nowej
	 * generacji.
	 * 
	 * @param parent1
	 *            Chromosom pierwszego rodzica.
	 * @param parent2
	 *            Chromosom drugiego rodzica.
	 * @return Zwraca liste chromosomow z dwoma elementami - potomkow
	 */
	public List<Chromosome> crossover(Chromosome parent1, Chromosome parent2) {

		List<Chromosome> children = new ArrayList<>();

		String parentCode1 = parent1.getBinaryCode();
		String parentCode2 = parent2.getBinaryCode();

		int crossoverPoint = generator.nextInt(parentCode1.length() - 1);

		String children1BinaryCode = parentCode1.substring(0, crossoverPoint)
				+ parentCode2.substring(crossoverPoint);
		String children2BinaryCode = parentCode2.substring(0, crossoverPoint)
				+ parentCode1.substring(crossoverPoint);

		children.add(new Chromosome(children1BinaryCode, this.data));
		children.add(new Chromosome(children2BinaryCode, this.data));

		return children;

	}

	/**
	 * Metoda, zgodnie z prawdopodobienstwem mutacji, dokonuje zmiany wartosci
	 * genu w chromosomie na przeciwna (z 0 na 1 lub z 1 na 0). Gen, ktory
	 * podlega mutacji, jest wybierany losowo.
	 * 
	 * @param chromosome
	 *            Chromosom podlegajacy mutacji.
	 * @return Nowy chromosom.
	 */
	private Chromosome mutation(Chromosome chromosome) {
		String newBinaryCode = chromosome.getBinaryCode();
		int index = generator.nextInt(newBinaryCode.length());

		if (newBinaryCode.charAt(index) == '0') {
			newBinaryCode = newBinaryCode.substring(0, index)
					+ "1"
					+ newBinaryCode
							.substring(index + 1, newBinaryCode.length());
		} else {
			newBinaryCode = newBinaryCode.substring(0, index)
					+ "0"
					+ newBinaryCode
							.substring(index + 1, newBinaryCode.length());
		}

		return new Chromosome(newBinaryCode, this.data);
	}

	/**
	 * Metoda wyszukuje najlepiej przystosowany chromosom.
	 * 
	 * @return Najlepiej przystosowany chromosom.
	 */
	private Chromosome getTheBestChromosome() {
		Chromosome theBest = this.population.get(0);

		for (int i = 1; i < this.population.size(); i++) {
			if (theBest.getFitness() > this.population.get(i).getFitness())
				theBest = this.population.get(i);
		}

		return theBest;
	}
}
